package arithmetic.demo14;

import java.util.*;

/**
 * 动态规划：dp + hash_最长定差子序列
 */

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        // 动态规划思想
        int  len = arr.length;
        // 使用hash来代替dp
        Map<Integer, Integer> hashDp = new HashMap<>(); // key = 元素 value = dp值

        // 初始化
        hashDp.put(arr[0], 1);
        int ret = 0;

        // 填表
        for(int i = 1; i < len; i++){
            int num = arr[i];

            if(hashDp.containsKey(num-difference)) {
                // 更新dp并且记录dp值
                hashDp.put(num, hashDp.get(num-difference) + 1);
            } else {
                hashDp.put(num, 1);
            }

            // 更新最终结果
            ret = Math.max(hashDp.get(arr[i]), ret);
        }

        return ret;
    }
}

/**
 * 方法二： 使用 map 中的 getOrDefault 方法
 */

class Solution1 {
    public int longestSubsequence(int[] arr, int difference) {
        // 动态规划思想
        int  len = arr.length;
        // 使用hash来代替dp
        Map<Integer, Integer> hashDp = new HashMap<>(); // key = 元素 value = dp值
        int ret=0;

        // 填表
        for(int num : arr){

            // 更新dp并且记录dp值
            hashDp.put(num,hashDp.getOrDefault(num-difference,0)+1);

            // 更新最终结果
            ret = Math.max(hashDp.get(num), ret);
        }

        return ret;
    }
}

 class Test {
     public static void main(String[] args) {
         Solution solution = new Solution();
         System.err.println(solution.longestSubsequence(new int[]{7, 7, 7, 7, 7, 7, 7}, 0));
         System.out.println("Test.main");
         System.out.println("args = " + Arrays.deepToString(args));
         System.out.println("solution = " + solution);

     }
 }

/**
 * 动态规划： 二维的两个数据的状态表示+hash：最长的斐波那契子序列的长度
 */

class Solution2 {
    public int lenLongestFibSubseq(int[] arr) {
        int len = arr.length;

        // 创建dp
        int[][] dp = new int[len][len];
        // 并且使用 map 来存储 key = 元素 ， value= 下标
        Map<Integer, Integer> hash  = new HashMap<>();
        int ret = 0;

        // 填表
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < i ; j++) {
                int target = arr[i]-arr[j];
                if(hash.containsKey(target) && hash.get(target) < j) {

                    // 判断元素存在并且下标是小于 j 的
                    int index = hash.get(target);

                    // 这里一定要注意次序， index 在 j 的前面
                    // j 在 i 的前面
                    dp[i][j] = dp[j][index] + 1;
                } else {

                    // 没有找到就置为 2
                    dp[i][j] = 2;
                }



                // 更新结果
                ret = Math.max(ret,dp[i][j]);
            }
            //存储的是i 位置的下标即可， 无论是否找到都要 存储到hash 中
            hash.put(arr[i],i);

        }
        return ret == 2 ? 0 : ret;

    }
}


/**
 * 动态规划:dp + hash + 从前往后遍历: 最长等差数列
 */

class Solution3 {
    public int longestArithSeqLength(int[] nums) {
        // 动态规划思想
        int len = nums.length;
        // 创建dp 和 hash
        int[][] dp = new int[len][len];
        Map<Integer,Integer> hash = new HashMap<>();

        int ret = 0;
        // 初始化
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < len; j++) {
                // 都置为2
                dp[i][j] = 2;
            }
        }
        // 填表
        for(int j = 0; j < len;j++) {

            for(int i = j + 1; i < len; i++) {
                // 查找是否存储等差
                int target = 2 * nums[j] - nums[i];
                if(hash.containsKey(target) && hash.get(target) < j) {
                    // 查找到就更新
                    int index = hash.get(target);
                    dp[i][j] = dp[j][index] + 1;
                }

                // 更新结果
                ret = Math.max(ret,dp[i][j]);
            }
            // 存入哈希
            hash.put(nums[j],j);
        }
        return ret;
    }
}

/**
 *  动态规划:dp+ 子数组:等差数列的划分
 */
class Solution4 {
    public int numberOfArithmeticSlices(int[] nums) {
        // 动态规划的思想
        int len = nums.length;
        // 特殊情况判断
        if(len < 3) {
            return 0;
        }

        // 创建dp
        int[] dp = new int[len];
        int ret = 0;



        for(int i = 2; i < len; i++) {
            // 出现时才进行迭代 否则默认为 0
            if(nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
                // 不断迭代
                dp[i] = dp[i-1] + 1;
            }
            // 计算结果
            ret += dp[i];
        }
        return ret;
    }
}

/**
 * 动态规划: dp + hash + list下标数组 : 等差数列的划分_子序列
 */

class Solution5 {
    public int numberOfArithmeticSlices(int[] nums) {
        int len = nums.length;

        // 创建dp
        int[][] dp = new int[len][len];
        int ret = 0;
        // key = 元素 value = 下标数组
        Map<Long, List<Integer>> hash = new HashMap<>();

        for (int i = 0; i < len; i++) {
            Long num = nums[i] + 0L;
            // 存储下标数组
            if (!hash.containsKey(num)) {
                // 如果不存在
                hash.put(num, new ArrayList<Integer>());
            }
            // 无论是否存在都需要添加下标
            hash.get(num).add(i);

            for (int j = 0; j < i; j++) {
                // 防止计算时溢出的必要举措
                long target = 2 * (nums[j] + 0L) - nums[i];
                if (hash.containsKey(target)) {
                    // 遇到的话就当前位置连接起来
                    List<Integer> tmp = hash.get(target);
                    for (int k : tmp) {
                        // 注意这里一定要添加判断结果, 有可能出现的下标的个数是在j的右边的
                        if (k < j) {
                            dp[i][j] += (dp[j][k] + 1);
                        } else {
                            // 如果前面都不存在了就直接跳出
                            break;
                        }
                    }
                }

                // 累加结果
                ret += dp[i][j];
            }

        }
        return ret;
    }
}